本题来自力扣169. 多数元素。难度：简单

暴力字典

创建一个字典，键值对中键为数字，值为改数字出现的个数，最后选出众数即可

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

排序

多数元素是指出现次数＞ n/2次的数，那么将列表排序之后，第n/2个数字就一定是那个数字。[1,1,1,1,2,3,4]  [1,2,3,4,4,4,4]。

当这个众数为最小值或者最大值排序之后第n/2个数字都是这个众数，那么说明如果众数是其他普通数字的话，第n/2个数字肯定也是众数。

[1,2,3,3,3,3,4] ，因为其他数字本身排序后就更靠近中间。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

投票算法

既然多数元素是指出现次数＞ n/2次的数，那么它 肯定比其他任何数都要多，可以想象一个投票场景，列表里的数字都看成候选人，如果列表里数字相同了，说明他们是一伙的自然会相互支持，数字不同了，就会投反对的票。

设置一个记录票数的变量count，赞成+1，反对-1。

如果count为1的时候，就代表那个候选人可以成功坐在椅子上，如果为0 的话就得退位，换下一个人来，如果下一个人来的时候椅子上没人（count=0）就可以直接坐上去,

且自己给自己投一票（每个人必须投出去自己的票要么赞成要么反对，自己肯定赞成自己）

如果有人的话（count>0)他可以投出一个反对的票，那么当这个人投完反对票后下下一个人就可以直接坐上椅子

因为此时count=0,一次类推，如果下下下一个人赞成的话count就+1，反对继续换人。

因为多数元素它们那一伙的人数比其他帮派的都多，其他人上位他们一定会反对(count-1)，自己人上位一定支持（count+1),到时候位置上自然就是自己人了。

比如：[1,1,1,2,2,2,2]这七个人编号a,b,c,d,e,f,g

a上位count+=1,b赞成count+=1,c赞成count+=1,此时count=3

这时候另一伙人2来了，d反对count-=1,e反对count-=1,f反对count-=1

此时count=0,a下位，g来了椅子上没人，g上位

帮派2获胜

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None	#刚开始位置上不坐人可以直接上位

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate